//
// Created by Administrator on 2024/1/6.
//

// 查找第一个值等于给定值的元素
// 查找最后一个值等于给定值的元素
// 查找第一个大于等于给定值的元素
// 查找第一个大于给定值的元素

/*二分查找变形
 *查找第一个/ 最后一个值等于给定值的元素
 * OJ: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 *查找第一个/ 最后一个值大于等于给定值的元素
 *
 * 讲解:  http://t.csdnimg.cn/uspHf
 * https://www.cnblogs.com/sunshuyi/p/12681088.html
 * */


#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    // 查找第一个和 最后一个值等于给定值的元素
    vector<int> searchRange(vector<int> &nums, int target)
    {
        vector<int> ret;
        int left = 0, right = nums.size() - 1;
        int mid;
        while (left <= right)
        {
            mid = (left + right) >> 1;
//        cout << left << mid << right << endl;
            if (target > nums[mid])
            {
                left = mid + 1;
            } else if (target < nums[mid])
            {
                right = mid - 1;
            } else
            {
                if (mid == 0 || nums[mid - 1] != target)
                {
                    ret.push_back(mid);
                    break;
                } else
                    right = mid - 1;
            }
        }
        if (ret.size() == 0)
            ret.push_back(-1);

        left = 0, right = nums.size() - 1;
        mid;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
//        mid = (left + right) >> 1;
            if (target > nums[mid])
                left = mid + 1;
            else if (target < nums[mid])
                right = mid - 1;
            else
            {
                if (mid >= nums.size() || nums[mid + 1] != target)
                {
                    ret.push_back(mid);
                    break;
                } else
                    left = mid + 1;
            }
        }
        if (ret.size() == 1)
        {
            ret.push_back(-1);
        }
        return ret;
    }
};

// 查找第一个值等于给定值的元素
int binarySearchForFirst(vector<int> &n, int target)
{
    int left = 0, right = n.size() - 1;
    int mid;
    while (left <= right)
    {
        mid = (left + right) >> 1;
//        cout << left << mid << right << endl;
            if (target > n[mid])
            {
                left = mid + 1;
            } else if (target < n[mid])
            {
                right = mid - 1;
            } else
            {
                if (mid == 0 || n[mid - 1] != target)
                    return mid;
                else
                    right = mid - 1;
        }
    }
    return -1;

}

// 查找最后一个值等于给定值的元素
int binarySearchForLast(vector<int> &n, int target)
{
    int left = 0, right = n.size() - 1;
    int mid;
    while (left <= right)
    {
        mid = left + (right - left) / 2;
//        mid = (left + right) >> 1;
        if (target > n[mid])
            left = mid + 1;
        else if (target < n[mid])
            right = mid - 1;
        else
        {
            if (mid >= n.size() || n[mid + 1] != target)
                return mid;
            else
                left = mid + 1;
        }
    }
    return -1;
}

// 查找第一个大于等于给定值的元素
int greaterEqualForFirst(vector<int> &n, int target)
{
    int l = 0, r = n.size() - 1;
    int mid = -1;
    if (target > n[r])
        return mid;
    while (l <= r)
    {
        mid = l + (r - l) / 2;
        if (target < n[mid])
        {
            r = mid - 1;
        } else if (target > n[mid])
        {
            l = mid + 1;
        } else
        {
            if (mid == 0 || n[mid - 1] != target)
                return mid;
            else
                r = mid - 1;
        }
    }
    return mid;
}

// 查找第一个大于给定值的元素
int greaterForFirst(vector<int> &n, int target)
{
    int l = 0, r = n.size()-1;
    int m = -1, t = r;
    if (n[r]<target)
        return m;
    while(l<=r)
    {
        m = (r+l)/2;
        if (target<n[m])
        {
            t = m;
            r=m-1;
        } else{
            l = m+1;
        }
    }
    return t;
}

int main()
{
    //                0   1  2  3  4  5  6  7  8  9  10 11  12
    vector<int> l = {-11, 0, 0, 1, 1, 1, 2, 2, 3, 5, 7, 9, 10};
//    l={1};
    int target =0;
//    cout << binarySearchForFirst(l, target)<<endl;
//    cout << binarySearchForLast(l, target)<<endl;
//    Solution s;
//    vector<int> r;
//    r=s.searchRange(l,target);
//    cout << greaterEqualForFirst(l, target) << endl;
    cout << greaterForFirst(l, target) << endl;
    return 0;
}